A mobile station (or user equipment; UE) that is connected to an EUTRAN (Evolved Universal Terrestrial Radio Access Network) base station, for example for user data reception or transmission, may lose this connection for several reasons. The UE might detect a radio link failure, handover or reconfiguration might fail or an integrity check fails. In all failed cases listed above the mobile station may desire to perform a reestablishment Procedure trying to reconnect. The UE may perform this reestablishment on the old serving cell that the UE was connected to or even on a different cell. This includes cells on same EUTRA frequency or different EUTRA frequency. For this reestablishment procedure, the UE may synchronize on the cell and send an RRC Connection Reestablishment Request message to the base station trying to reestablish the connection. This procedure may be cumbersome, and it may be desired to get a connection with the base station with a limited number of tries. Thus, there may be a need for devices and methods that provide an efficient Reestablishment Procedure.